"""
实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
"""
class LFUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = Item(size=0)
        # 为了方便查找索引
        self.idx = []

    def get(self, key):
        # 如果有这个索引
        if self.idx.count(key) == 1:
            item = self.getItemByIndex(key)
            item.count()
            self.putToHead(item)
            return item.value
        else:
            return -1

    # 每次有put或者get操作, 把被操作节点放到头节点, 这样最后一个节点一定是最久未使用的且cnt最小的
    def put(self, key, value):
        # 如果容量为0
        if self.capacity == 0:
            return
        # 如果没满
        if self.cache.size < self.capacity:
            # 如果链表里没有该索引, 直接头插
            if self.idx.count(key) == 0:
                # 头插
                item = Item(key, value)
                item.count()
                item.next = self.cache.next
                self.cache.next = item
                # 总数量++
                self.cache.size += 1
                # 索引置1
                self.idx.append(key)
            # 如果有该索引, 替换值, cnt++, 头插
            elif self.idx.count(key) == 1:
                # 找到这个节点
                p = self.getItemByIndex(key)
                # 替换值
                p.value = value
                # cnt++
                p.count()
                # 把这个节点放到头部
                self.putToHead(p)
        else:
            # 如果满了
            # 如果有索引
            if self.idx.count(key) == 1:
                # 找到这个节点
                p = self.getItemByIndex(key)
                # 替换值
                p.value = value
                # cnt++
                p.count()
                # 把这个节点放到头部
                self.putToHead(p)
            else:
                self.delMinItem()
                # 插入新节点
                self.cache.size += 1
                item = Item(key, value)
                item.count()
                item.next = self.cache.next
                self.cache.next = item
                self.idx.append(key)

    def getItemByIndex(self, key):
        # 指向第一个节点
        p = self.cache.next
        toFind = p.key
        while toFind != key:
            p = p.next
            toFind = p.key
        return p

    # 找到cnt最小的元素, 删除.如果有多个, 那删掉cnt最小的节点最靠后的那一个
    def delMinItem(self):
        pre = self.cache
        p = self.cache.next
        toDelete = p
        minCnt = p.cnt
        # 还没有到最后一个元素
        while p:
            # 如果p指向节点的value比当前minCnt小或者等于
            if minCnt >= p.cnt:
                # 更改指向
                minCnt = p.cnt
                toDelete = p
            # 继续往下查找
            pre = p
            p = p.next
        # toDelete就要删除的节点
        # 找到该节点的前一个节点
        pre_to_del = self.cache
        p_to_del = self.cache.next
        while p_to_del != toDelete:
            pre_to_del = p_to_del
            p_to_del = p_to_del.next
        # 删除
        self.idx.remove(p_to_del.key)
        pre_to_del.next = p_to_del.next
        p_to_del.next = None
        self.cache.size -= 1



    def putToHead(self, item):
        pre = self.cache
        p = self.cache.next
        # 如果只有一个节点
        if p.next == None:
            return
        # 找到这个节点前面的节点
        while p != item:
            pre = p
            p = p.next
        pre.next = p.next
        p.next = self.cache.next
        self.cache.next = p

# cache中元素的类型, 采用链式存储
class Item:
    def __init__(self, key=None, value=None, size=0):
        self.key = key
        self.value = value
        self.cnt = 0
        self.next = None
        # 作为头节点时方便计数
        self.size = size
    def count(self):
        self.cnt += 1


obj = LFUCache(2)
obj.put(2, 1)
obj.put(2, 2)
print(obj.get(2))
obj.put(1, 1)
obj.put(2, 1)
print(obj.get(2))

"""

# 双哈希实现
class Node(object):
    """
    双链表中的链表节点对象
    """

    def __init__(self, key=None, value=None, freq=0):
        """
        Args:
            key:对应输入的key
            value:对应输入的value
            freq:被访问的频率
            pre:指向前一个节点的指针
            next:指向后一个节点的指针
        """
        self.key = key
        self.value = value
        self.freq = freq
        self.pre = None
        self.next = None


class LinkedList(object):
    """
    自定义的双向链表
    """

    def __init__(self):
        """
        Args:
            __head:双向链表的头结点
            __tail:双向链表的尾节点
        """
        self.__head = Node()
        self.__tail = Node()
        self.__head.next = self.__tail
        self.__tail.pre = self.__head

    def insertFirst(self, node):
        """
        将指定的节点插入到链表的第一个位置
        Args:
            node:将要插入的节点
        """
        node.next = self.__head.next
        self.__head.next.pre = node
        self.__head.next = node
        node.pre = self.__head

    def delete(self, node):
        """
        从链表中删除指定的节点
        Args:
            node:将要删除的节点
        """
        if self.__head.next == self.__tail:
            return
        node.pre.next = node.next
        node.next.pre = node.pre
        node.next = None
        node.pre = None

    def getLast(self):
        """
        从链表中获取最后一个节点
        Returns:
            双向链表中的最后一个节点，如果是空链表则返回None
        """
        if self.__head.next == self.__tail:
            return None
        return self.__tail.pre

    def isEmpty(self):
        """
        判断链表是否为空，除了head和tail没有其他节点即为空链表
        Returns:
            链表不空返回True，否则返回False
        """
        return self.__head.next == self.__tail


class LFUCache(object):
    """
    自定义的LFU缓存
    """

    def __init__(self, capacity):
        """
        Args:
            __capacity:缓存的最大容量
            __keyMap: key->Node 这种结构的字典
            __freqMap:freq->LinkedList 这种结构的字典
            __minFreq:记录缓存中最低频率
        """
        self.__capacity = capacity
        self.__keyMap = dict()
        self.__freqMap = dict()
        self.__minFreq = 0

    def get(self, key):
        """
        获取一个元素，如果key不存在则返回-1，否则返回对应的value
        同时更新被访问元素的频率
        Args:
            key:要查找的关键字
        Returns:
            如果没找到则返回-1，否则返回对应的value
        """
        if key not in self.__keyMap:
            return -1
        node = self.__keyMap[key]
        self.__increment(node)
        return node.value

    def put(self, key, value):
        """
        插入指定的key和value，如果key存在则更新value，同时更新频率
        如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素
        否则，直接插入新元素
        Args:
            key:要插入的关键字
            value:要插入的值
        """
        if key in self.__keyMap:
            node = self.__keyMap[key]
            node.value = value
            self.__increment(node)
        else:
            if self.__capacity == 0:
                return
            if len(self.__keyMap) == self.__capacity:
                self.__removeMinFreqElement()
            node = Node(key, value, 1)
            self.__increment(node, True)
            self.__keyMap[key] = node

    def __increment(self, node, is_new_node=False):
        """
        更新节点的访问频率
        Args:
            node:要更新的节点
            is_new_node:是否是新节点，新插入的节点和非新插入节点更新逻辑不同
        """
        if is_new_node:
            self.__minFreq = 1
            self.__setDefaultLinkedList(node)
        else:
            self.__deleteNode(node)
            node.freq += 1
            self.__setDefaultLinkedList(node)
            if self.__minFreq not in self.__freqMap:
                self.__minFreq += 1

    def __setDefaultLinkedList(self, node):
        """
        根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
        Args:
            node:将要插入到LinkedList的节点
        """
        if node.freq not in self.__freqMap:
            self.__freqMap[node.freq] = LinkedList()
        linkedList = self.__freqMap[node.freq]
        linkedList.insertFirst(node)

    def __deleteNode(self, node):
        """
        删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
        Args:
            node:将要删除的节点
        """
        if node.freq not in self.__freqMap:
            return
        linkedList = self.__freqMap[node.freq]
        freq = node.freq
        linkedList.delete(node)
        if linkedList.isEmpty():
            del self.__freqMap[freq]

    def __removeMinFreqElement(self):
        """
        删除频率最低的元素，从__freqMap和__keyMap中都要删除这个节点，如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
        """
        linkedList = self.__freqMap[self.__minFreq]
        node = linkedList.getLast()
        linkedList.delete(node)
        del self.__keyMap[node.key]
        if linkedList.isEmpty():
            del self.__freqMap[node.freq]

